#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

//446. 等差数列划分 II - 子序列
//https://leetcode.cn/problems/arithmetic-slices-ii-subsequence/description/
// class Solution {
// public:
//     int numberOfArithmeticSlices(vector<int>& nums) {
//         int n = nums.size();

//         //数组中可能有很多重复的数 我们需要快速确定其下标 且值可能很大 使用long long
//         unordered_map<long long, vector<int>> m;
//         for (int i = 0; i < n; ++i) m[nums[i]].push_back(i); //建立值和下标数组的映射关系

//         //1 2 3
//         //a b c   a = 2b-c 
//         //使用二维数组存储 表示b c为结尾的数列子序列个数 默认为0个子序列
//         vector<vector<int>> vv(n, vector<int>(n));
//         int ret = 0;
//         for (int i = 2; i < n; ++i) //确定倒数第一个数下标
//         {
//             for (int j = 1; j < i; ++j) //j从1开始 如果从0开始 则 i j无法组成等差数列(不足3个)
//             {
//                 long long num = (long long)2 * nums[j] - nums[i]; //根据公式a=2b-c
//                 if (m.count(num)) //如果这个数存在 则开始遍历这个数的下标数组
//                 {
//                     for (const auto& x : m[num])//取出该数的下标 依次遍历
//                         if (x < j) vv[j][i] += vv[x][j] + 1; //每一个重复值后面都可以加上当前的数j凑成子序列

//                     //因为我们要求下标x不能在j之前，否则不符合要求 只能是 x j i 的顺序
//                 }
//                 ret += vv[j][i];
//             }
//         }
//         return ret;
//     }
// };


//回文子串
//https://leetcode.cn/problems/palindromic-substrings/description/
// class Solution {
// public:
//     int countSubstrings(string s) {
//         int n = s.size();

//         //二维数组表示 以开始i j结束 的序列是否是回文子串
//         vector<vector<bool>> vv(n,vector<bool>(n));

//         int ret = 0;

//         for(int i = n-1;i>=0;--i) //从最后开始验证 防止越界 i为起始位置
//             for(int j = i;j<n;++j) // [i,j] 段字符串开始验证
//             {
//                 if(s[i] == s[j]) //如果两个字符相等
//                     //如果i==j 或 i+1<j 则是 a或aa的情况 都是回文 否则需要缩小范围继续判断
//                     vv[i][j] = i+1<j?vv[i+1][j-1]:true;

//                 if(vv[i][j]) ++ret;
//             }
//         return ret;
//     }
// };

//最⻓回⽂⼦串
//https://leetcode.cn/problems/longest-palindromic-substring/submissions/
// class Solution {
// public:
//     string longestPalindrome(string s) {
//         int n = s.size();
//         vector<vector<bool>> vv(n, vector<bool>(n));

//         int x = 0;
//         int y = 0;
//         for (int i = n - 1; i >= 0; --i)
//             for (int k = i; k < n; ++k)
//             {
//                 if (s[i] == s[k])
//                     vv[i][k] = i + 1 < k ? vv[i + 1][k - 1] : true;
//                 if (vv[i][k] && (k - i) > (y - x)) { x = i; y = k; }
//             }

//         return s.substr(x, y - x + 1);
//     }
// };